<?php
/**
 * @title 1004. 最大连续1的个数 III - 合并+滑动窗口
 * @author start2004
 */

// ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer
     */
    function longestOnes($nums, $k) {
        /**
         * @since 2024-01-08 错误案例49
         */
        // $nums = explode(",", file_get_contents("/tmp/leetcode/1004-49.txt"));
        // $k = 4410; // 20000

        /**
         * @since 2024-01-08 格式化数组
         */
        $numArray = [];

        /**
         * @since 2024-01-08 数组个数
         */
        $numsCount = count($nums);

        /**
         * @since 2024-01-08 nums数组格式化一下
         */
        for($i=0; $i<$numsCount; $i++){
            /**
             * @since 2024-01-08 元素和元素个数
             */
            $num = $nums[$i];
            $count = 1;

            /**
             * @since 2024-01-08 相同元素的个数
             */
            while($i+1<$numsCount AND $nums[$i+1] == $num){
                $count++;
                $i++;
            }

            /**
             * @since 2024-01-08 记录数量
             */
            $numArray[] = [$num, $count];
            // echo "[{$num}, {$count}], ";
        }
        // echo PHP_EOL;die();
        // return $numArray;

        if(count($numArray) == 1 AND $numArray[0][0] == 0){
            return min($k, $numArray[0][1]);
        } else {}

        /**
         * @since 2024-01-08 连续1个个数，最大值
         */
        $maxOneCount = 0;

        /**
         * @since 2024-01-08 滑动窗口左右边界
         */
        $right = 0;

        /**
         * @since 2024-01-08 滑动窗口内0的个数
         */
        $zeroCount = 0;

        /**
         * @since 2024-01-08 遍历格式化数组
         */
        for($i=0; $i<count($numArray); $i++) {
            if($numArray[$i][0] == 0){
                continue;
            } else {}

            /**
             * @since 2024-01-08 滑动窗口右边界，没覆盖下标i，重新计算
             */
            if($right <= $i){
                /**
                 * @since 2024-01-08 初始化0的数量
                 */
                $right = $i;
                $zeroCount = 0;
                $oneCount = $numArray[$i][1];
            } else {
                /**
                 * @since 2024-01-08 right>i，[i, right]之间0的数量
                 */
                $zeroCount -= $numArray[$i-1][1];
                $oneCount = $oneCount - $numArray[$i-2][1] - $numArray[$i-1][1];
            }
            // echo "i={$i}, right={$right}, zeroCount={$zeroCount}, oneCount={$oneCount}, iK=", ($k-$zeroCount) ,"\n";

            /**
             * @since 2024-01-08 开始翻转0
             */
            $iK = $k-$zeroCount;
            for($j=$right+1; $j<count($numArray); $j++){
                // echo "j={$j}, iK={$iK}, numArray[j][0]={$numArray[$j][0]}, numArray[j][1]={$numArray[$j][1]}\n";
                
                /**
                 * @since 2024-01-08 连续1，直接累加
                 */
                if($numArray[$j][0] == 1){
                    $oneCount += $numArray[$j][1];
                } elseif($numArray[$j][0] == 0) {
                    /**
                     * @since 2024-01-08 遇到0，但已不够完全翻转
                     */
                    if($iK < $numArray[$j][1]){
                        $right = $j-1;
                        break;
                    } elseif($iK >= $numArray[$j][1]){
                        /**
                         * @since 2024-01-08 0，完全翻转
                         */
                        $iK -= $numArray[$j][1];
                        $oneCount += $numArray[$j][1];
                        $zeroCount += $numArray[$j][1];
                    } else {}
                } else {}
            }

            /**
             * @since 2024-01-08 如果iK还有值
             */
            // echo "iK={$iK}\n";
            if($iK > 0){
                /**
                 * @since 2024-01-08 i前和j的0的数量
                 */
                $c = 0;
                if(isset($numArray[$i-1])){
                    $c += $numArray[$i-1][1];
                } else {}
                if(isset($numArray[$j])){
                    $c += $numArray[$j][1];
                } else {}

                /**
                 * @since 2024-01-08 还可以翻转0的数量
                 */
                $addCount = min($iK, $c);
            } else {
                $addCount = 0;
            }

            /**
             * @since 2024-01-08 更新连续1的个数，最大值
             */
            // echo "j={$j}, count(numArray)= ", count($numArray), "\n";
            // echo "oneCount = {$oneCount}, addCount ={$addCount}, count=", ($oneCount+$addCount), PHP_EOL, PHP_EOL;
            $maxOneCount = max($maxOneCount, $oneCount+$addCount);

            /**
             * @since 2024-01-08 遍历到底，break
             */
            if($j == count($numArray)){
                break;
            } else {}
        }

        /**
         * @return
         */
        return $maxOneCount;
    }
}


/**
 * @url http://127.0.0.1/leetcode/202401/2024.01.08_9.php
 */
$datas = [
    // [[1,1,1,0,0,0,1,1,1,1,0], 2], // 6
    [[1,0,0,0,1,1,0,0,1,1,0,0,0,0,0,0,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,1,0,0,1,1,0,1,1], 8], // 25
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    if(count($data) <= 20){
        var_dump($data);
    } else {
        var_dump(count($data));
    }

    $obj = new Solution();
    $result = $obj->longestOnes(...$data);
    // $result = $obj->($xhprof->tree($data));
    // $result = $obj->($xhprof->listNode($data));
    // $result = $obj->find(...$data);
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat(PHP_EOL, 3);
    echo str_repeat("<br>", 3);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $func = $data[0][$i];
//         $param = $data[1][$i];
//         $result = $obj->$func(...$param);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
